package LeetCode.String;

//5 leetcode409. 最长回文串

/**
 * 给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
 * 在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。
 * 注意:假设字符串的长度不会超过 1010。
 * 示例 1:
 * 输入:"abccccdd"
 * 输出:7
 * 解释:我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
 */
public class Test5 {

    /**
     * 官方题解：
     *对于每个字母，假设它出现了 v 次。我们可以让 v // 2 * 2 个字母左右对称。
     * 例如，对于字符串 'aaaaa'，其中 'aaaa' 是左右对称，其长度为 5 // 2 * 2 = 4。
     * 最后，如果有任何一个满足 v % 2 == 1 的 v，那么这个字符就可能是回文串中唯一的那个中心。
     * 针对这种情况，我们需要判断 v % 2 == 1 && ans % 2 == 0，后面的判断主要是为了防止重复计算。
     */
    public static int longestPalindrome1(String s) {
        int[] count = new int[128];
        for (char c: s.toCharArray())
            count[c]++;
        int ans = 0;
        for (int v: count) {
            ans += v / 2 * 2;
            if (v % 2 == 1 && ans % 2 == 0)
                ans++;
        }
        return ans;
    }


    //不记acsii码 写法
    // int a[52]={0}; for(int i=0;i<s.length();i++) if(s[i]>='a'&&s[i]<='z') a[s[i]-'a']++; else a[s[i]-'A'+26]++;
    //评论题解：对于中心的处理，只需要在最后判断一次就好，只要字符串长度是大于结果的，说明一定有不成对出现的，加一返回结果即可
    public static int longestPalindrome2(String s) {
        int[] count = new int[58];
        for(int i = 0;i<s.length();i++){
            count[s.charAt(i) - 'A']++;
        }
        int length = 0;
        for(int v: count){
            length += v / 2 * 2;
        }
        if(s.length() > length) length++;//
        return length;
    }




    public static int longestPalindrome(String s) {
        int[] account = new int[58];//字母类型 A65 Z90 a97 z122
        char[] arr = s.toCharArray();//String转char[]
        for (char c : arr) {
            account[c - 'A']++;
        }
        int length=0;
        Boolean isSingle=false;//是否含单独的字母
        for (int i : account) {
             if (i%2==1||(i==s.length()&&i%2==1)){
                 isSingle=true;
             }
            length+=i/2*2;//除2取整 再 乘2
        }
        if (isSingle){
            length++;
        }
        return length;
    }

    public static void main(String[] args) {
        System.out.println(longestPalindrome("abccccdd"));
        System.out.println(longestPalindrome("ccc"));
        System.out.println(longestPalindrome("ababababa"));
        System.out.println(longestPalindrome("zeusnilemacaronimaisanitratetartinasiaminoracamelinsuez"));
    }
}
